
//895.最大频率栈
class FreqStack {
    unordered_map<int,int> m; //存储每一个元素出现的次数
    vector<stack<int>> nums;  //存储出现次数相同的数字
public:
    FreqStack() {
        nums.push_back(stack<int>());   
    }
    
    void push(int val) {
        m[val]++;   //加入该数字
        if(m[val]==nums.size())  //栈的数量不够了
            nums.push_back({});
        nums[m[val]].push(val);
    }
    
    int pop() {
        int ret=nums.back().top();
        nums.back().pop();
        if(nums.back().size()==0) nums.pop_back();
        m[ret]--;
        return ret;
    }
};

/**
 * Your FreqStack object will be instantiated and called as such:
 * FreqStack* obj = new FreqStack();
 * obj->push(val);
 * int param_2 = obj->pop();
 */